//https://leetcode.cn/problems/ones-and-zeroes/
package codeRandomThoughts.Test474一和零;

public class Solution3 {
    public int findMaxForm(String[] strs, int m, int n) {
        //这个背包问题的容积有两个维度,咱们这里把i给省去了
        //dp[j][k]:前0-i个子集能组成的最大子集长度为dp[j][k],该子集中最多有j个0和k个1
        int[][] dp = new int[m + 1][n + 1];

        //初始化
        for (int i = 0; i < strs.length; i++) {
            int[] count = getCount(strs[i]);
            for (int j = m; j >= count[0]; j--) {
                for (int k = n; k >= count[1]; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - count[0]][k - count[1]] + 1);
                }
            }
        }
        return dp[m][n];
    }

    //求strs[i]里面0和1的个数
    public int[] getCount(String s) {
        char[] chars = s.toCharArray();
        int[] res = new int[2];
        for (char c : chars) {
            if (c == '0') res[0]++;
        }
        res[1] = chars.length - res[0];
        return res;
    }
}
